package datastructure; /**
 * @Author leecho
 * @Date: 2021/10/11 17:10
 * @Version 1.0
 */



/**
 * 首先要创建两个栈
 * - 一个数据栈
 * - 一个符号栈
 * 在符号栈中要进行判断
 * - 如果为空就直接放入
 * - 如果栈中已经有了符号，并且要入栈的符号的优先级小于已有的符号
 *  - 就进行数据栈的数据出栈的操作和符号栈目前栈顶的符号出栈，进行运算，算出的结果，入数据栈
 *  - 再把当前扫描到的符号，入符号栈
 * - 如果扫描到的符号大于目前符号栈的栈顶的符号，则直接入栈
 *
 * 最后把剩下数据栈和符号栈中的出栈，运算，最后数据栈的栈顶得到的数据就是计算的结果
 * */
public class CalaDemo {
    public static void main(String[] args) {
        Cala numStack = new Cala(10);
        Cala symbolStack = new Cala(10);

        String in = "7*3-2*4";

        /*
        * 思路
        * - 这里是将传入的字符串利用字符串的方法进行分割
        *   - 定义一个index分割每一个字符，入栈结束以后index++扫描下一个
        * - 如果扫描到的是一个符号则进行上面说的进行判断
        * - 因为判断中有出栈和压栈需要一个变量来保存结果
        * */
        int index = 0;
        int oper = ' ';
        int num1 = 0;
        int num2 = 0;
        int res = 0;
        char c = ' ';

        while (true){
            // 扫描字符
            c = in.substring(index, index + 1).charAt(0);
            // 扫描出的结果是符号
            if (symbolStack.isOper(c)){
                // 如果为空则直接加入
                if (symbolStack.isEmpty()){
                    symbolStack.popStack(c);
                // 否则进行和当前符号栈中已经存在的符号进行比较
                } else {
                    // 如果当前扫描的符号小于栈顶的符号
                    if (symbolStack.compareOper(c)){
                        num1 = numStack.pushStack();
                        num2 = numStack.pushStack();
                        oper = symbolStack.pushStack();
                        res = numStack.resNum(num1, num2, oper);
                        numStack.popStack(res);
                        symbolStack.popStack(c);
                    } else {
                        symbolStack.popStack(c);
                    }
                }
            } else {
                // 这里的c可能还是字符，要转为数字则需要进行减去48，依据Unicode编码
                numStack.popStack(c- 48);
            }
            index++;
            if (index >= in.length()){
                break;
            }
        }

        // 将符号栈中的剩下的所有压入数据栈中最后得到一个结果
        while (true){
            if (symbolStack.isEmpty()){
                break;
            } else {
                num1 = numStack.pushStack();
                num2 = numStack.pushStack();
                oper = symbolStack.pushStack();
                res = numStack.resNum(num1,num2,oper);
                numStack.popStack(res);
            }
        }
        numStack.listStack();
    }
}

class Cala {
    /*
    * 思路
    * - 通过数组来创建一个栈
    * - 初始化一个变量为-1，当压入一个数据时向上移动一次，这样这个变量始终都是栈顶
    * */
    private int[] stack;
    private int top = -1;
    private int maxSize;

    public Cala(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    public boolean isEmpty(){
        return top == -1;
    }

    public int getTop(){
        return stack[top];
    }

    public boolean isFull(){
        return top == maxSize - 1;
    }

    public void popStack(int n){
        if (isFull()) {
            System.out.println("已满，无法添加");
            return;
        } else {
            top++;
            stack[top] = n;
        }

    }

    public int pushStack(){
        if (isEmpty()){
            throw new RuntimeException("当前栈为空，无法出栈");
        }else {
            int value = stack[top];
            top--;
            return value;
        }
    }

    public void listStack(){
        if (isEmpty()){
            System.out.println("目前空，无法出栈");
            return;
        }
        while (top >= 0){
            System.out.println(stack[top]);
            top--;
        }
    }

    public boolean isOper(char c){
        return c == '+' || c == '/' || c == '*' || c == '-';
    }

    public int priority(int c){
        if (c == '*' || c == '/'){
            return 1;
        } else if (c == '+' || c == '-')
            return 0;
        else
            return -1;
    }

    public boolean compareOper(char c){
        if (priority(c) <=  priority(getTop())){
            return true;
        } else
            return false;
    }

    public int resNum(int num1, int num2, int oper){
        int res = 0;
        switch (oper){
            case '+':
                res = num2 + num1;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num2 * num1;
                break;
            case '/':
                res = num2 / num1;
                break;
        }
        return res;
    }
}